그래프 동형사상

두 그래프가 동형이라면 반드시 만족해야 하는 성질들을 필요조건이라고 한다. 이러한 조건들은 동형임을 증명하는 데는 부족하지만, 두 그래프가 동형이 *아님*을 판별하는 데 유용하게 사용된다. 즉, 필요조건 중 하나라도 만족하지 않으면 두 그래프는 명백히 동형이 아니다.

주요한 필요조건은 다음과 같다. 첫째, 두 그래프는 정점의 수와 간선의 수가 각각 같아야 한다. 둘째, 각 정점의 차수(연결된 간선의 수)를 내림차순이나 오름차순으로 나열한 차수 시퀀스가 일치해야 한다. 셋째, 그래프의 연결 요소 개수, 지름, 색수와 같은 그래프 불변량들이 서로 같아야 한다.

이러한 조건들은 그래프의 전체적인 구조를 완벽히 포착하지는 못한다. 차수 시퀀스가 같은 두 그래프가 동형이 아닐 수 있으며, 모든 불변량이 일치하더라도 동형임이 보장되지 않는다. 따라서 필요조건들은 동형 후보를 빠르게 걸러내는 필터 역할을 하며, 보다 정밀한 판별을 위한 전처리 단계로 활용된다.

일반적인 그래프에 대한 동형사상의 충분조건은 명확하게 규정하기 어렵다. 동형사상 불변량이 일치한다고 해서 항상 동형사상이 성립하는 것은 아니기 때문이다. 예를 들어, 정점 수, 간선 수, 차수 시퀀스가 동일한 두 그래프가 서로 동형사상이 아닐 수 있다. 따라서 이러한 불변량들은 필요조건일 뿐이며, 두 그래프가 동형사상임을 증명하는 충분조건을 찾는 것은 그래프 동형 문제의 핵심이다.

동형사상을 판별하는 알고리즘은 크게 두 가지 범주로 나눌 수 있다. 첫 번째는 실용적으로 널리 사용되는 알고리즘으로, NAUTY와 같은 소프트웨어가 대표적이다. 이 알고리즘은 정점을 색칠하고 분할하며, 정규형을 계산하여 두 그래프의 정규형이 일치하는지 비교하는 방식을 사용한다. 두 번째 범주는 이론적 복잡도에 중점을 둔 알고리즘으로, 2015년에 라슬로 바바이가 제안한 준다항식 시간 알고리즘이 유명하다. 이 알고리즘은 그래프 동형 문제가 NP-완전 문제가 아니라는 강력한 증거를 제공했다.

이러한 알고리즘들은 일반적으로 백트래킹과 정점 분할 세분화 기법을 결합하여 가능한 모든 정점 매핑을 효율적으로 탐색한다. 알고리즘의 성능은 그래프의 구조에 크게 의존하며, 특정 그래프 클래스에서는 다항식 시간 내에 문제를 해결할 수 있다. 예를 들어, 유계 차수 그래프나 평면 그래프에 대해서는 효율적인 알고리즘이 알려져 있다.

따라서 두 그래프의 동형사상을 확인하는 확실한 방법은 이러한 전문 알고리즘을 이용해 계산적으로 검증하는 것이다. 현재까지 일반 그래프에 대해 다항식 시간 알고리즘이 발견되지 않았기 때문에, 이 문제는 계산 이론에서 중요한 미해결 문제로 남아 있다.

트리 동형사상은 두 트리 그래프가 동형인지를 판별하는 특수한 문제이다. 일반 그래프의 동형사상 문제는 복잡도가 명확히 규명되지 않은 반면, 트리 동형사상 문제는 다항식 시간 내에 해결 가능한 것으로 알려져 있다. 이는 트리가 사이클이 없는 단순한 계층적 구조를 가지기 때문이다.

트리 동형사상을 판별하는 대표적인 알고리즘은 AHU 알고리즘이다. 이 알고리즘은 각 정점에 대해 그 서브트리의 구조를 나타내는 고유한 문자열 또는 코드를 재귀적으로 계산한다. 두 트리의 루트 정점에 부여된 코드가 동일하면 두 트리는 동형으로 판단한다. 이 방법은 트리의 크기에 대해 선형 시간 복잡도를 가진다.

루트 없는 트리, 즉 루트가 지정되지 않은 트리의 동형사상 판별은 먼저 트리의 중심 또는 중앙축을 찾아 이를 새로운 루트로 삼은 후, AHU 알고리즘을 적용하는 방식으로 해결할 수 있다. 트리 동형사상 알고리즘은 XML 문서 비교, 컴파일러의 구문 트리 분석, 분자 그래프 중 트리 구조를 가진 것의 비교 등 다양한 분야에서 활용된다.

평면 그래프 동형사상은 두 평면 그래프가 동형인지를 판별하는 특수한 문제이다. 일반적인 그래프 동형 문제는 복잡도 이론에서 그 정확한 위치가 명확하지 않은 난제로 남아 있지만, 평면 그래프에 대해서는 다항식 시간 내에 해결할 수 있는 효율적인 알고리즘이 존재한다는 점에서 중요한 의미를 가진다.

이 문제를 해결한 대표적인 알고리즘은 1970년대에 존 호프크로프트와 로버트 타잔이 제안한 것으로 알려져 있다. 이 알고리즘은 평면 그래프의 고유한 구조적 특성, 특히 평면성과 이중 그래프의 관계를 활용하여 정점들을 체계적으로 분류하고 비교한다. 이를 통해 두 평면 그래프가 위상적으로 동일한 평면 임베딩을 가지는지, 즉 정점과 간선의 연결 관계를 보존하면서 평면에 그릴 수 있는 구조가 일치하는지를 판단할 수 있다.

평면 그래프 동형사상 판별의 상대적 용이성은 평면 그래프가 가지는 강력한 제약 조건에서 비롯된다. 평면 그래프는 쿠라토프스키 정리에 의해 완전 그래프 K5나 완전 이분 그래프 K3,3을 위상적 마이너로 포함하지 않는다는 특징이 있으며, 이러한 제약이 그래프의 구조를 보다 엄격하게 규정한다. 결과적으로, 두 평면 그래프가 동형인지를 확인하기 위해 고려해야 할 가능한 정점 매핑의 경우의 수가 일반 그래프에 비해 훨씬 제한적이게 되어 효율적인 판별이 가능해진다.

이 분야의 연구는 계산 기하학 및 위상 그래프 이론과도 깊이 연관되어 있다. 평면 그래프의 동형사상을 판별하는 것은 결국 그래프의 평면 매너시를 고려한 구조적 동치성을 찾는 문제이며, 이는 자동 형식 증명 시스템이나 VLSI 설계와 같은 실용적인 분야에서도 응용 가능성을 가진다.

정규 그래프 동형사상은 모든 정점의 차수가 동일한 정규 그래프 간의 동형사상 문제를 다룬다. 정규 그래프는 각 정점이 동일한 수의 이웃을 가지므로, 차수 시퀀스와 같은 기본적인 그래프 동형 불변량만으로는 동형 여부를 판별하기 어렵다. 이는 문제의 복잡성을 높이는 요인으로 작용한다. 예를 들어, 서로 다른 두 정규 그래프가 동일한 수의 정점과 간선, 그리고 동일한 차수를 가질 수 있지만, 실제로는 서로 동형이 아닐 수 있다.

이러한 특성 때문에 일반 그래프 동형 문제보다 더 어렵거나, 반대로 특정 조건에서 더 쉽게 풀릴 수 있다는 연구 결과가 존재한다. 일부 연구에서는 강한 정규 그래프와 같이 추가적인 대칭성을 가진 그래프 클래스에서 다항식 시간 내에 동형사상을 판별할 수 있는 알고리즘이 제안되기도 했다. 그러나 대부분의 일반적인 정규 그래프에 대해서는 여전히 효율적인 알고리즘이 알려져 있지 않으며, 이 문제의 계산 복잡도는 그래프 동형 문제의 복잡도와 밀접하게 연관되어 있다.

정규 그래프 동형사상 문제는 순열군과 행렬 이론, 그룹 이론 등 다양한 수학적 도구를 활용하여 접근한다. 특히 그래프의 자기 동형사상 군을 분석하는 것이 중요한 단서가 될 수 있다. 두 그래프가 동형이기 위해서는 그들의 자기 동형사상 군이 서로 동형이어야 한다는 것은 필요조건이지만, 충분조건은 아니다.

자기 동형사상은 그래프가 자기 자신과 동형인 경우, 즉 그래프의 정점들을 재배열하는 동형사상을 의미한다. 수학적으로, 그래프 G = (V, E)의 자기 동형사상은 정점 집합 V에서 V로 가는 전단사 함수 f이며, 모든 정점 u, v ∈ V에 대해 {u, v}가 간선일 필요충분조건이 {f(u), f(v)}가 간선인 경우를 말한다. 이는 그래프의 구조적 대칭성을 수학적으로 표현하는 개념이다.

모든 그래프는 항상 적어도 하나의 자기 동형사상을 가지며, 이를 자명한 자기 동형사상이라고 한다. 이는 모든 정점을 자기 자신에 대응시키는 항등 함수에 해당한다. 만약 자명한 자기 동형사상 외에 다른 자기 동형사상이 존재한다면, 해당 그래프는 비자명한 대칭성을 가진다고 말할 수 있다. 예를 들어, 완전 그래프나 정다각형 모양의 순환 그래프는 매우 풍부한 자기 동형사상 군을 가진다.

그래프의 모든 자기 동형사상의 집합은 함수의 합성 연산 아래에서 군을 이루며, 이를 그래프의 자기 동형사상 군이라고 한다. 이 군의 크기와 구조는 그래프의 대칭성의 정도를 정량화한다. 자기 동형사상 군의 연구는 대수적 그래프 이론의 주요 주제 중 하나이며, 군론과 대수학의 도구를 활용한다.

이 개념은 그래프 동형 문제와도 밀접하게 연관되어 있다. 두 그래프가 동형인지 판별하는 문제는, 두 그래프의 합성 그래프를 만들고 그 자기 동형사상 군을 분석하는 방식으로 접근하기도 한다. 또한, 화학 정보학에서 분자 구조의 대칭성을 분석하거나, 네트워크 분석에서 복잡계의 숨겨진 패턴을 발견하는 데 응용된다.

동형사상 불변량은 그래프의 구조적 속성 중에서 동형인 그래프들 사이에 반드시 동일한 값을 가지는 것을 말한다. 즉, 두 그래프가 동형이라면 그들의 불변량 값은 같아야 한다. 반대로 불변량 값이 다르다면 두 그래프는 동형이 아님을 확실히 알 수 있다. 그러나 불변량 값이 같다고 해서 항상 동형임을 보장하지는 않는다. 이러한 성질 때문에 불변량은 주로 그래프 동형사상 문제에서 두 그래프가 *다를* 가능성을 빠르게 걸러내는 데 활용된다.

주요한 그래프 동형사상 불변량에는 다음과 같은 것들이 있다.

이러한 불변량들은 계산 복잡도가 다양하다. 정점 수나 간선 수처럼 단순히 세기만 하면 되는 불변량도 있는 반면, 채색수나 그래프 스펙트럼을 계산하는 것은 NP-난해 문제에 속하거나 행렬 계산이 필요해 상대적으로 복잡하다. 따라서 실제 동형사상 판별 알고리즘에서는 여러 불변량을 조합하여 사용하며, 특히 계산이 빠르고 필터링 능력이 좋은 불변량을 우선적으로 적용한다.

동형사상 불변량의 연구는 그래프 이론의 기본적인 주제 중 하나이며, 화학 정보학에서 분자 구조를 표현하는 분자 그래프를 비교하거나, 네트워크 과학에서 복잡한 시스템의 구조적 유사성을 분석하는 등 다양한 응용 분야의 기초를 제공한다.